Field-Programmable Gate Arrays (FPGAs), generally include circuitry that can be configured to behave as different user-defined hardware designs. FPGAs in which K-input Look-Up Tables (LUTs) are used as elementary logic blocks have been used universally since the 1980s. In general, K-input LUTs are generic blocks which can implement particular logic functions of K-inputs. Particular circuitry may be mapped in an FPGA by covering the circuitry with K-input subgraphs, irrespective of the functionality that the circuitry represents.
However, increasing the number of LUT inputs to cover larger parts of a circuit has an exponential cost in the LUT complexity. The area of a LUT generally increases exponentially with the number of inputs to the LUT, which disadvantageously takes up substantial amounts of chip real estate. Also, disadvantageously, the delay introduced by a LUT grows linearly with the number of inputs to the LUT. Thus, LUTs with more than 4-6 inputs are rarely used. Further, because LUTs intrinsically have only one output, internal fan-out of subgraphs can not be performed using LUTs to cover a particular circuitry.
Alternate FPGA structures have been proposed based on logic synthesis capabilities at various times. Such alternate FPGA structures have almost universally been based on addressed programmable AND/OR configurations in the form of small Programmable Array Logics (PALs) to implement sum of products representations and algebraic transformations, for example.
One proposed FPGA structure includes small PAL-like structures, with 7-10 inputs and 10-13 product terms, for example. Such structures have been found to obtain performance gains at the price of an increase in area. Another proposed FPGA structure includes K-input multiple-output PAL-style logic blocks. Such structures have been found to be more area efficient than 4-input LUTs but generally consume an unacceptable amount of static power.
Yet another proposed FPGA structure includes an “extended” logic element with slightly modified K-input LUTs to reduce the tile area needed for a logic block. In one example, the addition of an AND gate on the LUT output produces an extended K-LUT. Implementations of such an extended K-LUT on the area of a K-LUT have provided the performance of a K+1-LUT. Such increased performance could facilitate further advantages such as reduced wire lengths, reduced interconnect capacitance and reduced delay, for example, however disadvantages of LUT structures generally remain.
Reconfigurable logic blocks have been adapted for specific FPGA implementations by adding dedicated logic gates to existing LUTs. Various other application specific FPGA configurations have been proposed or implemented. However, such configurations that are specific to various fields or applications have not been practical for more general FPGA implementations.